package com.gitee.feizns.explore.data_structure.linked_list.singly.mergeKLists;

/**
 * @author feizns
 * @since 2020/3/2
 */
public class MergeKLists {

    public static void main(String[] args) {
        println(mergeKLists(new ListNode[]{ create(), create1() }));
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode ret = new ListNode(-1);
        ListNode tmp = ret;
        int min;
        ListNode minNode;
        while ((min = min(lists)) != -1 && (minNode = lists[min]) != null) {
            tmp.next = minNode;
            lists[min] = minNode.next;
            tmp = tmp.next;
        }
        return ret.next;
    }

    private static int min(ListNode... list) {
        if ( list == null || list.length == 0 ) return -1;
        int min = -1;
        for (int i = 0; i < list.length; i++) {
            if ( min == -1 || list[min] == null || (list[i] != null && list[i].val < list[min].val) )
                min = i;
        }
        return min;
    }

    private static ListNode create() {
        ListNode q = new ListNode(0);
        q.next = new ListNode(1);
        q.next.next = new ListNode(2);
        return q;
    }

    private static ListNode create1() {
        ListNode q = new ListNode(0);
        q.next = new ListNode(1);
        q.next.next = new ListNode(2);
        return q;
    }

    private static void println(ListNode re) {
        ListNode t = re;
        while ( t != null ) {
            System.out.print(t.val);
            t = t.next;
        }
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
